﻿\subsection{Как это работает}

Из школьной математики, мы можем вспомнить, что деление на 9 может быть заменено на умножение на $\frac{1}{9}$.
На самом деле, для чисел с плавающей точкой, иногда компиляторы так и делают,
например, инструкциея \INS{FDIV} в x86-коде может быть заменена на \INS{FMUL}.
По крайней мере MSVC 6.0 заменяет деление на 9 на умножение на $0.111111...$ и иногда нельзя быть уверенным в том,
какая операция была в оригинальном исходном коде.

Но когда мы работаем с целочисленными значениями и целочисленными регистрами CPU, мы не можем использовать дроби.
Но мы можем переписать дробь так:

% FIXME: equation size
\begin{center}
$result = \frac{x}{9} = x \cdot \frac{1}{9} = x \cdot \frac{1 \cdot MagicNumber}{9 \cdot MagicNumber}$
\end{center}

Учитывая тот факт, что деление на $2^n$ очень быстро (при помощи сдвигов), теперь нам нужно найти такой $MagicNumber$,
для которого следующее уравнение будет справедливо: $2^n = 9 \cdot MagicNumber$.

Деление на $2^{32}$ в каком-то смысле скрыто: младшие 32 бита произведения в EAX не используются (выкидываются),
только старшие 32 бита произведения (в EDX) используются и затем сдвигаются еще на 1 бит.

Другими словами, только что увиденный код на ассемблере умножает на {\Large $\frac{954437177}{2^{32+1}}$},
или делит на {\Large $\frac{2^{32+1}}{954437177}$}.
Чтобы найти делитель, нужно просто разделить числитель на знаменатель.
Используя Wolfram Alpha, мы получаем результат 8.99999999.... (что близко к 9).

% TODO ref to https://yurichev.com/blog/signed_division_using_shifts/

Читайте больше об этом в \InSqBrackets{\HenryWarren 10-3}.

Еще кое что для лучшего понимания.
Многие люди не замечают ``скрытое'' деление на $2^{32}$ или $2^{64}$,
когда младшая 32-битная часть произведения (или 64-битная) не используется.
Также, имеется недоразумение, что здесь используется обратное число по модулю.
Это близко, но не то же самое.
Для поиска \textit{магического коэффициента}, часто используется расширенный алгоритм Эвклида, но на самом деле,
этот алгоритм используется для решения уравнения.
Вы можете решать его его любым другим методом.
Так или иначе, расширенный алгоритм Эвклида наверное самый эффективный метод решения.
Также, нужно упомянуть, что уравнение не решаемо для некоторых делителей, потому что это диофантово уравнение
(т.е., уравнение в котором результат может быть только целым числом), так как, все же, мы работаем с целочисленными
регистрами CPU.

